home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / D-G / GemsI / Original / LineEdgeIntersect.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-16  |  3.8 KB  |  125 lines  |  [TEXT/MPS ]
  1. /* 
  2. Fast Line-Edge Intersections on a Uniform Grid 
  3. by Andrew Shapira
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. #include "GraphicsGems.h"
  8.  
  9. #define OCTANT(f1, f2, f3, f4, f5, i1, s1, r1, r2) \
  10.     for (f1, f2, f3, nr = 0; f4; f5) { \
  11.         if (nr < const) { \
  12.             if (i1) \
  13.                 r1(&C); \
  14.             else \
  15.                 vertex(&C); \
  16.         } \
  17.         else { \
  18.             s1; \
  19.             if (nr -= const) { \
  20.                 r2(&C); \
  21.                 r1(&C); \
  22.             } \
  23.             else \
  24.                 vertex(&C); \
  25.         } \
  26.     }
  27.  
  28. find_intersections(Pptr, Qptr)
  29. IntPoint2   *Pptr, *Qptr;       /* P and Q as described in gem text */
  30. {
  31.     IntPoint2   P, Q;           /* P and Q, dereferenced for speed */
  32.     IntPoint2   C;              /* current grid point */
  33.     int         nr;             /* remainder */
  34.     int         deltax, deltay; /* Q.x - P.x, Q.y - P.y */
  35.     int         const;          /* loop-invariant constant */
  36.  
  37.     P.x = Pptr->x;
  38.     P.y = Pptr->y;
  39.     Q.x = Qptr->x;
  40.     Q.y = Qptr->y;
  41.     deltax = Q.x - P.x;
  42.     deltay = Q.y - P.y;
  43.  
  44.  
  45.     /* for reference purposes, let theta be the angle from P to Q */
  46.  
  47.     if ((deltax >= 0) && (deltay >= 0) && (deltay < deltax)) 
  48.                                 /* 0 <= theta < 45 */
  49.         OCTANT(C.x = P.x + 1, C.y = P.y, const = deltax - deltay, 
  50.                 C.x < Q.x, C.x++, nr += deltay, C.y++, up, left)
  51.     else if ((deltax > 0) && (deltay >= 0) && (deltay >= deltax)) 
  52.                                /* 45 <= theta < 90 */
  53.         OCTANT(C.y = P.y + 1, C.x = P.x, const = deltay - deltax,
  54.                  C.y < Q.y, C.y++, nr += deltax, C.x++, right, down)
  55.     else if ((deltax <= 0) && (deltay >= 0) && (deltay > -deltax))
  56.                                /* 90 <= theta < 135 */
  57.         OCTANT(C.y = P.y + 1, C.x = P.x, const = deltay + deltax,
  58.                  C.y < Q.y, C.y++, nr -= deltax, C.x--, left, down)
  59.     else if ((deltax <= 0) && (deltay > 0) && (deltay <= -deltax)) 
  60.                                /* 135 <= theta < 180 */
  61.         OCTANT(C.x = P.x - 1, C.y = P.y, const = -deltax - deltay,
  62.                  C.x > Q.x, C.x--, nr += deltay, C.y++, up, right)
  63.     else if ((deltax <= 0) && (deltay <= 0) && (deltay > deltax))
  64.                               /* 180 <= theta < 225 */
  65.         OCTANT(C.x = P.x - 1, C.y = P.y, const = -deltax + deltay, 
  66.                 C.x > Q.x, C.x--, nr -= deltay, C.y--, down, right)
  67.     else if ((deltax < 0) && (deltay <= 0) && (deltay <= deltax))
  68.                               /* 225 <= theta < 270 */
  69.         OCTANT(C.y = P.y - 1, C.x = P.x, const = -deltay + deltax,
  70.                 C.y > Q.y, C.y--, nr -= deltax, C.x--, left, up)
  71.     else if ((deltax >= 0) && (deltay <= 0) && (-deltay > deltax))
  72.                              /* 270 <= theta < 315 */
  73.         OCTANT(C.y = P.y - 1, C.x = P.x, const = -deltay - deltax, 
  74.                 C.y > Q.y, C.y--, nr += deltax, C.x++, right, up)
  75.     else if ((deltax >= 0) && (deltay < 0) && (-deltay <= deltax))
  76.                              /* 315 <= theta < 360 */
  77.         OCTANT(C.x = P.x + 1, C.y = P.y, const = deltax + deltay,
  78.                  C.x < Q.x, C.x++, nr -= deltay, C.y--, down, left)
  79.     else {}                    /* P = Q */
  80. }
  81.  
  82. vertex(I)
  83. IntPoint2   *I;
  84. {
  85.     /* Note: replace printf with code to process vertex, if desired */
  86.     (void) printf("vertex at %d %d\n", I->x, I->y);
  87. }
  88.  
  89. left(I)
  90. IntPoint2   *I;
  91. {
  92.  
  93.     /* Note: replace printf with code to process leftward */     
  94.     /* intersection, if desired */
  95.     (void) printf("left from %d %d\n", I->x, I->y);
  96. }
  97.  
  98. up(I)
  99. IntPoint2   *I;
  100. {
  101.     /* Note: replace printf with code to process upward */
  102.     /* intersection, if desired */
  103.     (void) printf("up from %d %d\n", I->x, I->y);
  104. }
  105.  
  106. right(I)
  107. IntPoint2   *I;
  108. {
  109.     /* Note: replace printf with code to process rightward */
  110.     /* intersection, if desired */
  111.     (void) printf("right from %d %d\n", I->x, I->y);
  112. }
  113.  
  114. down(I)
  115. IntPoint2   *I;
  116. {
  117.     /* Note: replace printf with code to process downward */
  118.     /* intersection, if desired */
  119.     (void) printf("down from %d %d\n", I->x, I->y);
  120. }
  121.  
  122.  
  123.  
  124.  
  125.